'''
https://leetcode.cn/problems/generate-parentheses/description
'''
from collections import deque
from typing import List

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        res = []
        path = deque()
        def dfs(left, right):
            if left == 0:
                res.append(''.join(path) + ')' * right)
                return
            if left == right:   # 必须选左括号
                path.append('(')
                dfs(left - 1, right)
                path.pop()
            else:   # left < right, 可左可右
                if left:
                    path.append('(')
                    dfs(left - 1, right)
                    path.pop()
                path.append(')')
                dfs(left, right - 1)
                path.pop()
        dfs(n, n)
        return res


